#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import datetime


def prime_num(n):
    count = 2
    primes = [3]
    start = datetime.datetime.now()

    for i in range(5, n + 1, 2):
        is_prime = False
        edge = int(i**0.5)
        for x in primes:
            if x > edge:
                is_prime = True
                break
            if i % x == 0:
                is_prime = False
                break
        if is_prime:
            count += 1
            primes.append(i)

    primes.insert(0, 2)
    delta = (datetime.datetime.now() - start).total_seconds()
    print(len(primes))
    return delta, primes


# twin prime
# my answer
def twin_prime(n):
    primes = [2, 3]
    limit = (n // 6) + 1

    for i in range(1, limit):
        six_times_left = 6 * i - 1
        six_times_right = 6 * i + 1
        left_limit = six_times_left**0.5
        right_limit = six_times_right**0.5
        in_left = False
        in_right = False

        for prime in primes:
            if prime > left_limit:
                in_left = True
                break
            if six_times_left % prime == 0:
                in_left = False
                break

        for prime in primes:
            if prime > right_limit:
                in_right = True
                break
            if six_times_right % prime == 0:
                in_right = False
                break

        if in_left:
            primes.append(six_times_left)
        if in_right:
            primes.append(six_times_right)

    return primes


# teacher answer
def twin_prime1(n):
    primes = [2, 3, 5]
    step = 4
    x = 7

    while x < n:
        limit = x**0.5
        is_prime = False

        for i in primes:
            if i > limit:
                is_prime = True
                break
            if x % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(x)

        x += step
        # 变步长
        step = 4 if step == 2 else 2
    return primes


# c = twin_prime1(100000)
# print(twin_prime(1000))

# task 2
# yanghui triangle


def yanghui_1(n):
    triangle = [[1], [1, 1]]

    for i in range(2, n):
        cur = [1]
        prv = triangle[i - 1]
        for j in range(i - 1):
            cur.append(prv[j] + prv[j + 1])
        cur.append(1)
        triangle.append(cur)
    print(triangle)


def yanghui_2(n):
    triangle = []

    for i in range(n):
        cur = [1]
        triangle.append(cur)
        if i == 0:
            continue

        prev = triangle[i - 1]
        for j in range(i - 1):
            cur.append(prev[j] + prev[j + 1])

        cur.append(1)

    return triangle


# yanghui fill with zero
def yanghui_3(n=3):
    triangle = [[1], [1, 1]]
    for i in range(2, n):
        tri = []
        tri_prev = triangle[i - 1].copy()
        tri_prev.append(0)

        for i in range(-1, i):
            tri.append(tri_prev[i] + tri_prev[i + 1])
        triangle.append(tri)
    return triangle


# print(yanghui_3(10))


# yanghui 
def yanghui_4(n=3):
    triangle = [[1], [1, 1]]

    for i in range(2, n):
        tri = [1] * (i + 1)
        prev_tri = triangle[i - 1]

        for j in range(1, i // 2 + 1):
            tri[j] = prev_tri[j - 1] + prev_tri[j]
            tri[-j - 1] = tri[j]
        triangle.append(tri)
    return triangle


yanghui_4(10)
